
package com.liwt.pongo;

/**
 * 来自庞果网： <h2>
 * 给定一个包含1-n的数列，我们通过交换任意两个元素给数列重新排序。求最少需要多少次交换，能把数组排成按1-n递增的顺序，其中，数组长度不超过100。</h2>
 * <p>
 * 例如： 原数组是3,2,1， 我们只需要交换1和3就行了，交换次数为1，所以输出1。
 * <p>
 * 原数组是2,3,1，我们需要交换2和1，变成1,3,2，再交换3和2，变为1，2，3，总共需要的交换次数为2，所以输出2。
 * 
 * @author likebamboo
 * @create 2013-10-17
 * @see http://blog.csdn.net/likebamboo/article/details/12836543
 * @mind <p>
 *       遍历数列,如果发现i位置的元素a[i]不在正确的位置(即a[i]!=i+1)，
 *       <p>
 *       那么将a[i]替换到正确的位置j(a[i]的正确位置应该在j = a[i]-1);
 *       <p>
 *       j位置的元素换到i位置，重新从i位置开始遍历.
 *       <p>
 *       该算法的时间复杂度为O(N+m) ，m为原数列中不在正确位置的元素的个数。空间复杂度为O(1)
 */
public class ArrSort {

    public static int run(int a[]) {
        int count = 0, temp;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > a.length) {
                System.out.println("测试数据非法，数组中的数必须是小于等于N(N为数组的长度)，而且不重复的。");
            }
            if (a[i] != i + 1) {// 改元素没有在正确的位置上，将它替换到正确的位置。
                count++;
                temp = a[i];
                a[i] = a[temp - 1];
                a[temp - 1] = temp;
                i--; // 再次从该位置开始。
            }
        }
        return count;
    }

    /**
     * 该算法为错误方法 ，其思路为：
     * <p>
     * case 1：a[i] = i 的，不用交换； 假设有n1个
     * <p>
     * case 2：a[a[i]] = i 的， 也就是a[3] = 6, a[6] = 3 只需交换一次 ， 假设有n2 个。一对算2个。
     * <p>
     * case 3：剩下的是一个追逐式的循环， 假设有n3个，当n3 > 0时，需要交换n3 - 1次，否则不用交换
     * <p>
     * 那么，当n3 > 0时，结果为 n2 / 2 + n3 - 1。 当n3 = 0 时， 结果为 n2 / 2
     * <p>
     * 针对这个数列 1,3,5,6,2,7,4, 应该四次就可以OK，而该算法要五次,错
     * 
     * @param a
     * @return
     */
    public static int run_error(int[] a) {
        int n2 = 0, n3 = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] > a.length) {
                System.out.println("输入数据非法,数据不连续" + a[i] + " --" + a.length);
                return -1;
            }
            if (a[i] == i + 1) {
            } else if (a[a[i] - 1] == i + 1) {
                n2++;
            } else {
                n3++;
            }
        }

        if (n3 > 1) {
            return n2 / 2 + n3 - 1;
        }
        return n2 / 2;
    }

    public static void main(String[] args) {
        int[] a = {
                93, 52, 12, 70, 25, 36, 18, 37, 27, 99, 68, 40, 84, 3, 76, 57, 60, 19, 33, 41, 92,
                87, 58, 13, 15, 43, 28, 63, 64, 59, 31, 97, 14, 69, 4, 88, 72, 65, 10, 23, 67, 81,
                21, 80, 90, 82, 74, 1, 95, 42, 89, 29, 53, 44, 17, 61, 50, 8, 85, 73, 30, 62, 7,
                46, 54, 77, 9, 34, 38, 16, 26, 56, 71, 32, 83, 48, 49, 11, 91, 35, 24, 75, 78, 20,
                86, 45, 94, 55, 98, 2, 39, 96, 5, 22, 100, 6, 79, 66, 51, 47
        };

        System.out.println(run(a));
    }
}
